package com.jxb.sort;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 希尔排序
 * 1：获取增量序列
 * 2：根据增量序列进行分组
 * 3：对每个分组进行插入排序
 *
 * @author jiaobo
 * @date Created in 2024/12/12 20:00
 **/
public class ShellSort {

    public static void main(String[] args) {
        int[] nums = {1,4,3,6,0,4,5,9,4,2,6};
        System.out.println("排序开始----------------->" + Arrays.toString(nums));
        int[] res = sortArray(nums);
        System.out.println("排序结束----------------->" + Arrays.toString(res));
    }

    public static int[] sortArray(int[] nums) {
        //获取增量序列
        Queue<Integer> is = new LinkedList();
        int el = nums.length;
        while (el != 1) {
            el = el/2;
            is.offer(el);
        }
        //通过增量序列进行排序
        while (!is.isEmpty()) {
            Integer curIs = is.poll();
            //当前待排序的数据
            int currentValue;
            for (int i = 0;i<nums.length-curIs;i = i+curIs) {
                //已被排序的数据索引
                int preIndex = i;
                //获取当前需要排序的数据
                currentValue = nums[preIndex + curIs];
                while (preIndex >= 0 && currentValue<nums[preIndex]) {
                    //将已排序的数据向后移动一位
                    nums[preIndex + curIs] = nums[preIndex];
                    preIndex =  preIndex - curIs;
                }
                nums[preIndex + curIs] = currentValue;
            }
        }
        return nums;


    }

}
